package hot100;

import java.util.Arrays;

public class Lc33 {
    public int search(int[] nums, int target) {
        int rotateIdx = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                rotateIdx = i + 1;
                break;
            }
        }
        int ret;
        ret = this.binarySearchEQ(Arrays.copyOfRange(nums, 0, rotateIdx), target);
        if (ret >= 0) {
            return ret;
        }
        ret = this.binarySearchEQ(Arrays.copyOfRange(nums, rotateIdx, nums.length), target);
        if (ret >= 0) {
            return ret + rotateIdx;
        }
        return -1;
    }

    private int binarySearchEQ(int[] nums, int target) {
        int left = -1;
        int right = nums.length;
        while (left + 1 < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] > target) {
                right = mid;
            }
            else {
                left = mid;
            }
        }
        return -right - 1;
    }
}
